SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Symmetric Turing machine</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Symmetric Turing machine</span></span>

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1126788409">

/* start https://en.wikipedia.org/ */

.mw-parser-output .plainlist ol,.mw-parser-output .plainlist ul{line-height:inherit;list-style:none;margin:0;padding:0}.mw-parser-output .plainlist ol li,.mw-parser-output .plainlist ul li{margin-bottom:0}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1246091330">

/* start https://en.wikipedia.org/ */

.mw-parser-output .sidebar{width:22em;float:right;clear:right;margin:0.5em 0 1em 1em;background:var(--background-color-neutral-subtle,#f8f9fa);border:1px solid var(--border-color-base,#a2a9b1);padding:0.2em;text-align:center;line-height:1.4em;font-size:88%;border-collapse:collapse;display:table}body.skin-minerva .mw-parser-output .sidebar{display:table!important;float:right!important;margin:0.5em 0 1em 1em!important}.mw-parser-output .sidebar-subgroup{width:100%;margin:0;border-spacing:0}.mw-parser-output .sidebar-left{float:left;clear:left;margin:0.5em 1em 1em 0}.mw-parser-output .sidebar-none{float:none;clear:both;margin:0.5em 1em 1em 0}.mw-parser-output .sidebar-outer-title{padding:0 0.4em 0.2em;font-size:125%;line-height:1.2em;font-weight:bold}.mw-parser-output .sidebar-top-image{padding:0.4em}.mw-parser-output .sidebar-top-caption,.mw-parser-output .sidebar-pretitle-with-top-image,.mw-parser-output .sidebar-caption{padding:0.2em 0.4em 0;line-height:1.2em}.mw-parser-output .sidebar-pretitle{padding:0.4em 0.4em 0;line-height:1.2em}.mw-parser-output .sidebar-title,.mw-parser-output .sidebar-title-with-pretitle{padding:0.2em 0.8em;font-size:145%;line-height:1.2em}.mw-parser-output .sidebar-title-with-pretitle{padding:0.1em 0.4em}.mw-parser-output .sidebar-image{padding:0.2em 0.4em 0.4em}.mw-parser-output .sidebar-heading{padding:0.1em 0.4em}.mw-parser-output .sidebar-content{padding:0 0.5em 0.4em}.mw-parser-output .sidebar-content-with-subgroup{padding:0.1em 0.4em 0.2em}.mw-parser-output .sidebar-above,.mw-parser-output .sidebar-below{padding:0.3em 0.8em;font-weight:bold}.mw-parser-output .sidebar-collapse .sidebar-above,.mw-parser-output .sidebar-collapse .sidebar-below{border-top:1px solid #aaa;border-bottom:1px solid #aaa}.mw-parser-output .sidebar-navbar{text-align:right;font-size:115%;padding:0 0.4em 0.4em}.mw-parser-output .sidebar-list-title{padding:0 0.4em;text-align:left;font-weight:bold;line-height:1.6em;font-size:105%}.mw-parser-output .sidebar-list-title-c{padding:0 0.4em;text-align:center;margin:0 3.3em}@media(max-width:640px){body.mediawiki .mw-parser-output .sidebar{width:100%!important;clear:both;float:none!important;margin-left:0!important;margin-right:0!important}}body.skin--responsive .mw-parser-output .sidebar a>img{max-width:none!important}@media screen{html.skin-theme-clientpref-night .mw-parser-output .sidebar:not(.notheme) .sidebar-list-title,html.skin-theme-clientpref-night .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle{background:transparent!important}html.skin-theme-clientpref-night .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle a{color:var(--color-progressive)!important}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .sidebar:not(.notheme) .sidebar-list-title,html.skin-theme-clientpref-os .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle{background:transparent!important}html.skin-theme-clientpref-os .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle a{color:var(--color-progressive)!important}}@media print{body.ns-0 .mw-parser-output .sidebar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><table class="sidebar nomobile nowraplinks"><tbody><tr><th class="sidebar-title"><a href="Turing_machine" title="Turing machine">Turing machines</a></th></tr><tr><th class="sidebar-heading" style="background:#ddddff;">

Machine</th></tr><tr><td class="sidebar-content plainlist">

<ul><li><a href="Turing_machine_equivalents" title="Turing machine equivalents">Turing machine equivalents</a></li>

<li><a href="Turing_machine_examples" title="Turing machine examples">Turing machine examples</a></li></ul></td>

</tr><tr><th class="sidebar-heading" style="background:#ddddff;">

Variants</th></tr><tr><td class="sidebar-content plainlist">

<ul><li><a href="Alternating_Turing_machine" title="Alternating Turing machine">Alternating Turing machine</a></li>

<li><a href="Neural_Turing_machine" title="Neural Turing machine">Neural Turing machine</a></li>

<li><a href="Nondeterministic_Turing_machine" title="Nondeterministic Turing machine">Nondeterministic Turing machine</a></li>

<li><a href="Quantum_Turing_machine" title="Quantum Turing machine">Quantum Turing machine</a></li>

<li><a href="Post%E2%80%93Turing_machine" title="Post–Turing machine">Post–Turing machine</a></li>

<li><a href="Probabilistic_Turing_machine" title="Probabilistic Turing machine">Probabilistic Turing machine</a></li>

<li><a href="Multitape_Turing_machine" title="Multitape Turing machine">Multitape Turing machine</a></li>

<li><a href="Multi-track_Turing_machine" title="Multi-track Turing machine">Multi-track Turing machine</a></li>

<li><a href="Decider_(Turing_machine)" title="Decider (Turing machine)">Total Turing machine</a></li>

<li><a href="Unambiguous_Turing_machine" title="Unambiguous Turing machine">Unambiguous Turing machine</a></li>

<li><a href="Universal_Turing_machine" title="Universal Turing machine">Universal Turing machine</a></li>

<li><a href="Zeno_machine" title="Zeno machine">Zeno machine</a></li></ul></td>

</tr><tr><th class="sidebar-heading" style="background:#ddddff;">

Science</th></tr><tr><td class="sidebar-content plainlist">

<ul><li><a href="Alan_Turing" title="Alan Turing">Alan Turing</a></li>

<li>Category:Turing machine</li></ul></td>

</tr><tr><td class="sidebar-navbar"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></td></tr></tbody></table>

<p>A <b>symmetric Turing machine</b> is a <a href="Turing_machine" title="Turing machine">Turing machine</a> which has a <a href="Configuration_graph" title="Configuration graph">configuration graph</a> that is undirected (that is, configuration i yields configuration j if and only if j yields

i).

</p>

<div class="mw-heading mw-heading2"><h2 id="Definition_of_symmetric_Turing_machines">Definition of symmetric Turing machines</h2></div>

<p>Formally, we define a variant of Turing machines with a set of transitions of the form <span class="nowrap">⁠<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (p,ab,D,cd,q)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (p,ab,D,cd,q)}</annotation>

</semantics>

</math></span><img src="./ef836ee954f3243efdfc4f9db8d2bf527c32561e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.558ex; height:2.843ex;" alt="{\displaystyle (p,ab,D,cd,q)}" loading="lazy"></span>⁠</span>, where <i>p,q</i> are states, <i>ab,cd</i> are pairs of symbols and <i>D</i> is a direction. If <i>D</i> is <i>left</i>, then the head of a machine in state <i>p</i> above a tape symbol <i>b</i> preceded by a symbol <i>a</i> can be transitioned by moving the head left, changing the state to <i>q</i> and replacing the symbols <i>a,b</i> by <i>c,d</i>. The opposite transition <span class="nowrap">⁠<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (q,cd,-D,ab,p)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (q,cd,-D,ab,p)}</annotation>

</semantics>

</math></span><img src="./6554aa0e3c8c725960be1f7e2022b5031d2c75be.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.367ex; height:2.843ex;" alt="{\displaystyle (q,cd,-D,ab,p)}" loading="lazy"></span>⁠</span> can always be applied. If <i>D</i> is right the transition is analogous. The ability to peek at two symbols and change both at a time is non-essential, but makes the definition easier.

</p><p>Such machines were first defined in 1982 by <a href="Harry_R._Lewis" title="Harry R. Lewis">Harry R. Lewis</a> and <a href="Christos_Papadimitriou" title="Christos Papadimitriou">Christos Papadimitriou</a>,<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> who were looking for a class in which to place <a href="USTCON" class="mw-redirect" title="USTCON">USTCON</a>, the problem asking whether there is a path between two given vertices s,t in an undirected graph. Until this time, it could be placed only in <a href="NL_(complexity)" title="NL (complexity)">NL</a>, despite seeming not to require <a href="Nondeterministic_finite_automaton" title="Nondeterministic finite automaton">nondeterminism</a> (the asymmetric variant <a href="STCON" class="mw-redirect" title="STCON">STCON</a> was known to be complete for NL). Symmetric Turing machines are a kind of Turing machine with limited nondeterministic power, and were shown to be at least as powerful as deterministic Turing machines, giving an interesting case in between.

</p><p><span class="nowrap">⁠<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathsf {STIME}}(T(n))}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathsf {STIME}}(T(n))}</annotation>

</semantics>

</math></span><img src="./e7b5b20737d9061ed48dbb66e495140b356d4cc7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.593ex; height:2.843ex;" alt="{\displaystyle {\mathsf {STIME}}(T(n))}" loading="lazy"></span>⁠</span> is the class of the languages accepted by a symmetric Turing machine running in time <span class="nowrap">⁠<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(T(n))}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(T(n))}</annotation>

</semantics>

</math></span><img src="./149bbde1780ba6139461e6a34fd7f9b00ca0d5f4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.423ex; height:2.843ex;" alt="{\displaystyle O(T(n))}" loading="lazy"></span>⁠</span>. It can easily be proved that <span class="nowrap">⁠<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathsf {STIME}}(T)={\mathsf {NTIME}}(T)}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathsf {STIME}}(T)={\mathsf {NTIME}}(T)}</annotation>

</semantics>

</math></span><img src="./d06feea3df116463a855c9df7be5376619729abe.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:24.229ex; height:2.843ex;" alt="{\displaystyle {\mathsf {STIME}}(T)={\mathsf {NTIME}}(T)}" loading="lazy"></span>⁠</span> by limiting the nondeterminism of any machine in <span class="nowrap">⁠<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathsf {NTIME}}(T)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathsf {NTIME}}(T)}</annotation>

</semantics>

</math></span><img src="./0034861f57bf02ce7439a9fe84403782c138ddb4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.742ex; height:2.843ex;" alt="{\displaystyle {\mathsf {NTIME}}(T)}" loading="lazy"></span>⁠</span> to an initial stage where a string of symbols is nondeterministically written, followed by deterministic computations.

</p>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="SL_(complexity)" title="SL (complexity)">SL (complexity)</a></div>

<p><span style="font-family:sans-serif;">SSPACE</span>(S(<i>n</i>)) is the class of the languages accepted by a symmetric Turing machine running in space <span class="nowrap">⁠<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(S(n))}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(S(n))}</annotation>

</semantics>

</math></span><img src="./343ab759efff53825bd7fa57e82340d2b4d09bc7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.286ex; height:2.843ex;" alt="{\displaystyle O(S(n))}" loading="lazy"></span>⁠</span> and <span style="font-family:sans-serif;"><a href="SL_(complexity)" title="SL (complexity)">SL</a></span>=<span style="font-family:sans-serif;">SSPACE</span>(log(<i>n</i>)).

</p><p>SL can equivalently be defined as the class of problems <a href="Logspace" class="mw-redirect" title="Logspace">logspace</a> reducible to USTCON. Lewis and Papadimitriou by their definition showed this by constructing a nondeterministic machine for USTCON with properties that they showed are sufficient to make a construction of an equivalent symmetric Turing machine possible. Then, they observed that any language in SL is logspace reducible to USTCON as from the properties of the symmetric computation we can view the

special configuration as the undirected edges of the graph.

</p><p>In 2004, <a href="Omer_Reingold" title="Omer Reingold">Omer Reingold</a> proved that SL=L by showing a deterministic algorithm for USTCON running in logarithmic space,<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> for which he received the 2005 <a href="Grace_Murray_Hopper_Award" title="Grace Murray Hopper Award">Grace Murray Hopper Award</a> and (together with <a href="Avi_Wigderson" title="Avi Wigderson">Avi Wigderson</a> and <a href="Salil_Vadhan" title="Salil Vadhan">Salil Vadhan</a>) the 2009 <a href="G%C3%B6del_Prize" title="Gödel Prize">Gödel Prize</a>. The proof uses the <a href="Zig-zag_product" title="Zig-zag product">zig-zag product</a> to efficiently construct <a href="Expander_graph" title="Expander graph">expander graphs</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

<li id="cite_note-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-1">^</a></b></span> <span class="reference-text">Jesper Jansson. <a rel="nofollow" class="external text" href="http://www.df.lth.se/~jj/Publications/STCON2.ps">Deterministic Space-Bounded Graph Connectivity Algorithms</a>. Manuscript. 1998.</span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text">Harry R. Lewis and Christos H. Papadimitriou. Symmetric space-bounded computation. <i>Theoretical Computer Science</i>. pp.161-187. 1982.</span>

</li>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFReingold2008" class="citation cs2"><a href="Omer_Reingold" title="Omer Reingold">Reingold, Omer</a> (2008), "Undirected connectivity in log-space", <i><a href="Journal_of_the_ACM" title="Journal of the ACM">Journal of the ACM</a></i>, <b>55</b> (4): <span class="nowrap">1–</span>24, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1391289.1391291">10.1145/1391289.1391291</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2445014">2445014</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:207168478">207168478</a>, <a href="Electronic_Colloquium_on_Computational_Complexity" title="Electronic Colloquium on Computational Complexity">ECCC</a> <a rel="nofollow" class="external text" href="https://eccc.weizmann.ac.il/report/2004/094/">TR04-094</a></cite></span>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

<ul><li>Lecture Notes :CS369E: Expanders in Computer Science By Cynthia Dwork & Prahladh Harsha</li>

<li><a rel="nofollow" class="external text" href="http://www.cs.huji.ac.il/~advtheory">Lecture Notes</a></li>

<li>Sharon Bruckner Lecture Notes</li>

<li>Deterministic Space Bounded Graph connectivity Algorithms Jesper Janson</li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2024-06-19" href="https://en.wikipedia.org/wiki/?title=Symmetric_Turing_machine&oldid=1229866779">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>